package com.wdc.回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("all")
public class E06Leetcode131 {
    private List<List<String>> reslut = new ArrayList<>();
    private LinkedList<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {

        backTracking(s, 0);
        return reslut;
    }


    void backTracking(String s ,int startIndex){
        //递归结束条件
        if (startIndex >= s.length()){
            reslut.add(new ArrayList<>(path));
            return;
        }
        //循环宽度
        for (int i = startIndex; i < s.length(); i++) {
            //是否是回文
            if (isPalinrome(s,startIndex,i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            }else {
                continue;
            }
            //递归
            backTracking(s,i + 1);
            //回溯
            path.removeLast();

        }


    }

    boolean isPalinrome(String s,int startIndex , int end){
        for (int i = startIndex , j = end; i < j; i++ ,j--) {
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
